{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 暂时放弃、不太懂"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from copy import deepcopy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter:664\n",
      "w: [3.8083642640626554, 0.03486819339595951, 1.6400224976589866, -4.463151671894514, 1.7883062251202617, 5.308526768308639, -0.13398764643967714, -2.2539799445450406, 1.4840784189709668, -1.890906591367886, 1.933249316738729, -1.2629454476069037, 1.7257519419059324, 2.967849703391228, 3.9061632698216244, -9.520241584621713, -1.8736788731126397, -3.483844660866203, -5.637874599559359]\n",
      "predict: {'no': 2.819781341881656e-06, 'yes': 0.9999971802186581}\n"
     ]
    }
   ],
   "source": [
    "class MaxEntropy:\n",
    "    def __init__(self, EPS=0.005):\n",
    "        self._samples = []\n",
    "        self._Y = set()  # 标签集合，相当去去重后的y\n",
    "        self._numXY = {}  # key为(x,y)，value为出现次数\n",
    "        self._N = 0  # 样本数\n",
    "        self._Ep_ = []  # 样本分布的特征期望值\n",
    "        self._xyID = {}  # key记录(x,y),value记录id号\n",
    "        self._n = 0  # 特征键值(x,y)的个数\n",
    "        self._C = 0  # 最大特征数\n",
    "        self._IDxy = {}  # key为(x,y)，value为对应的id号\n",
    "        self._w = []\n",
    "        self._EPS = EPS  # 收敛条件\n",
    "        self._lastw = []  # 上一次w参数值\n",
    "\n",
    "    def loadData(self, dataset):\n",
    "        self._samples = deepcopy(dataset)\n",
    "        for items in self._samples:\n",
    "            y = items[0]\n",
    "            X = items[1:]\n",
    "            self._Y.add(y)  # 集合中y若已存在则会自动忽略\n",
    "            for x in X:\n",
    "                if (x, y) in self._numXY:\n",
    "                    self._numXY[(x, y)] += 1\n",
    "                else:\n",
    "                    self._numXY[(x, y)] = 1\n",
    "\n",
    "        self._N = len(self._samples)\n",
    "        self._n = len(self._numXY)\n",
    "        self._C = max([len(sample) - 1 for sample in self._samples])\n",
    "        self._w = [0] * self._n\n",
    "        self._lastw = self._w[:]\n",
    "\n",
    "        self._Ep_ = [0] * self._n\n",
    "        for i, xy in enumerate(self._numXY):  # 计算特征函数fi关于经验分布的期望\n",
    "            self._Ep_[i] = self._numXY[xy] / self._N\n",
    "            self._xyID[xy] = i\n",
    "            self._IDxy[i] = xy\n",
    "\n",
    "    def _Zx(self, X):  # 计算每个Z(x)值\n",
    "        zx = 0\n",
    "        for y in self._Y:\n",
    "            ss = 0\n",
    "            for x in X:\n",
    "                if (x, y) in self._numXY:\n",
    "                    ss += self._w[self._xyID[(x, y)]]\n",
    "            zx += math.exp(ss)\n",
    "        return zx\n",
    "\n",
    "    def _model_pyx(self, y, X):  # 计算每个P(y|x)\n",
    "        zx = self._Zx(X)\n",
    "        ss = 0\n",
    "        for x in X:\n",
    "            if (x, y) in self._numXY:\n",
    "                ss += self._w[self._xyID[(x, y)]]\n",
    "        pyx = math.exp(ss) / zx\n",
    "        return pyx\n",
    "\n",
    "    def _model_ep(self, index):  # 计算特征函数fi关于模型的期望\n",
    "        x, y = self._IDxy[index]\n",
    "        ep = 0\n",
    "        for sample in self._samples:\n",
    "            if x not in sample:\n",
    "                continue\n",
    "            pyx = self._model_pyx(y, sample)\n",
    "            ep += pyx / self._N\n",
    "        return ep\n",
    "\n",
    "    def _convergence(self):  # 判断是否全部收敛\n",
    "        for last, now in zip(self._lastw, self._w):\n",
    "            if abs(last - now) >= self._EPS:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def predict(self, X):  # 计算预测概率\n",
    "        Z = self._Zx(X)\n",
    "        result = {}\n",
    "        for y in self._Y:\n",
    "            ss = 0\n",
    "            for x in X:\n",
    "                if (x, y) in self._numXY:\n",
    "                    ss += self._w[self._xyID[(x, y)]]\n",
    "            pyx = math.exp(ss) / Z\n",
    "            result[y] = pyx\n",
    "        return result\n",
    "\n",
    "    def train(self, maxiter=1000):  # 训练数据\n",
    "        for loop in range(maxiter):  # 最大训练次数\n",
    "            self._lastw = self._w[:]\n",
    "            for i in range(self._n):\n",
    "                ep = self._model_ep(i)  # 计算第i个特征的模型期望\n",
    "                self._w[i] += math.log(self._Ep_[i] / ep) / self._C  # 更新参数\n",
    "            #print(\"w:\", self._w)\n",
    "            if self._convergence():  # 判断是否收敛\n",
    "                print(\"iter:%d\" % loop)\n",
    "                print(\"w:\", self._w)\n",
    "                break\n",
    "                \n",
    "dataset = [['no', 'sunny', 'hot', 'high', 'FALSE'],\n",
    "           ['no', 'sunny', 'hot', 'high', 'TRUE'],\n",
    "           ['yes', 'overcast', 'hot', 'high', 'FALSE'],\n",
    "           ['yes', 'rainy', 'mild', 'high', 'FALSE'],\n",
    "           ['yes', 'rainy', 'cool', 'normal', 'FALSE'],\n",
    "           ['no', 'rainy', 'cool', 'normal', 'TRUE'],\n",
    "           ['yes', 'overcast', 'cool', 'normal', 'TRUE'],\n",
    "           ['no', 'sunny', 'mild', 'high', 'FALSE'],\n",
    "           ['yes', 'sunny', 'cool', 'normal', 'FALSE'],\n",
    "           ['yes', 'rainy', 'mild', 'normal', 'FALSE'],\n",
    "           ['yes', 'sunny', 'mild', 'normal', 'TRUE'],\n",
    "           ['yes', 'overcast', 'mild', 'high', 'TRUE'],\n",
    "           ['yes', 'overcast', 'hot', 'normal', 'FALSE'],\n",
    "           ['no', 'rainy', 'mild', 'high', 'TRUE']]\n",
    "\n",
    "maxent = MaxEntropy()\n",
    "x = ['overcast', 'mild', 'high', 'FALSE']\n",
    "\n",
    "maxent.loadData(dataset)\n",
    "maxent.train()\n",
    "\n",
    "print('predict:', maxent.predict(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# key为(x,y)，value为出现次数\n",
    "19_numXY = {('sunny', 'no'): 3, ('hot', 'no'): 2, ('high', 'no'): 4, ('FALSE', 'no'): 2, ('TRUE', 'no'): 3, ('overcast', 'yes'): 4, ('hot', 'yes'): 2, ('high', 'yes'): 3, ('FALSE', 'yes'): 6, ('rainy', 'yes'): 3, ('mild', 'yes'): 4, ('cool', 'yes'): 3, ('normal', 'yes'): 6, ('rainy', 'no'): 2, ('cool', 'no'): 1, ('normal', 'no'): 1, ('TRUE', 'yes'): 3, ('mild', 'no'): 2, ('sunny', 'yes'): 2}\n",
    "\n",
    "#计算特征函数fi关于经验分布的期望  19_numXY/14样本个数\n",
    "19_Ep_ = [0.21428571428571427, 0.14285714285714285, 0.2857142857142857, 0.14285714285714285, 0.21428571428571427, 0.2857142857142857, 0.14285714285714285, 0.21428571428571427, 0.42857142857142855, 0.21428571428571427, 0.2857142857142857, 0.21428571428571427, 0.42857142857142855, 0.14285714285714285, 0.07142857142857142, 0.07142857142857142, 0.21428571428571427, 0.14285714285714285, 0.14285714285714285]\n",
    "\n",
    "# 计算第i个特征的模型期望 并更新权重_w\n",
    "ep = _model_ep(0-19) = \n",
    "_w = _w + log(19_Ep_/19_ep)/4_特征数\n",
    "\n",
    "#计算每个P(y|x)\n",
    "_model_pyx  在sunny的情况下，y=no的概率\n",
    "\n",
    "#计算每个Z(x)值\n",
    "_Zx(X)\n",
    "\n",
    "if sunny in 14个样本中的某一个：\n",
    "    计算P(y|x)     _model_pyx('no' , ['no', 'sunny', 'mild', 'high', 'FALSE']) pyx\n",
    "    计算每一个zx值   _Zx(['no', 'sunny', 'mild', 'high', 'FALSE'])  -> \n",
    "                    ( 'no' 'yes')( 'sunny' 'yes') ( 'mild' 'yes')( 'high' 'yes')是否在19_numXY中  ->计算ss+=_w->zx += exp(ss)\n",
    "                    ( 'no' 'no')( 'sunny' 'no') ( 'mild' 'no')( 'high' 'no')是否在19_numXY中  -> 计算ss+=_w->zx += exp(ss)\n",
    "    计算P(y|x)  ( 'no' 'no')( 'sunny' 'no') ( 'mild' 'no')( 'high' 'no')计算ss+=_w->pyx =  exp(ss)/zx\n",
    "    ep += pyx / self._N\n",
    "    \n",
    "    \n",
    "期望_损失 += log(19_特征经验分布期望/19_特征模型期望)/4_特征个数\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
